<html>
<head><meta charset="utf-8"><title>Performance tuning BTree · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html">Performance tuning BTree</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="222862360"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222862360" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222862360">(Jan 15 2021 at 14:17)</a>:</h4>
<p>Is there someone in this stream, or elsewhere on Zulip, whom I could ask a few questions on how to test a small performance tweak for BTree?</p>



<a name="222864057"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222864057" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222864057">(Jan 15 2021 at 14:30)</a>:</h4>
<p><span class="user-mention" data-user-id="257813">@Stein Somers</span> works on btree quite a lot, they might have suggestions</p>



<a name="222865438"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222865438" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222865438">(Jan 15 2021 at 14:40)</a>:</h4>
<p>Hi <span class="user-mention" data-user-id="257813">@Stein Somers</span>,</p>
<p>Do you know if someone ever tried to tune the node capacity? The benches for capacity 5 seem faster.</p>
<p>I was trying to use binary search in the nodes (as was suggested at the PR that merges the "branchless" version). That seemed faster. I suspected that with binary search, it would be worth increasing the capacity (was not the case). Then I noticed that with a smaller capacity, binary search was faster. So I tested linear search against that same capacity, and it was faster too (5 instead of 6). </p>
<p>Faster here is counting the number of tests that are faster.</p>
<p>Binary search seems to have a much lower variance, most of the time, which might be interested. A few test cases however have variance increased again by quite a bit (i.e. increased variance of variance, decreased mean of variance). So far, it looks like binary search could lead to a 5% improvement on average.</p>
<p>Finally, I thought that something might be wrong with my bench setup. E.g. by running one test after the other -&gt; different heat -&gt; different clock frequency -&gt; different ns.</p>



<a name="222869888"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222869888" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222869888">(Jan 15 2021 at 15:08)</a>:</h4>
<p>It would also be interesting to try a different order of elements, instead of  binary search over sorted node.<br>
I would start by looking to see what benchmarking was used in other PR's to the Btree file.</p>



<a name="222882674"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222882674" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222882674">(Jan 15 2021 at 16:25)</a>:</h4>
<p>You can disable turbo-boost to decrease variance if you're benchmarking wall clock time. Helps especially on thermally constrained laptops.<br>
Alternatively you can bench instructions, but I think the built-in bench still doesn't support that, you'll need some 3rd-party benchmark crate for that.</p>



<a name="222882822"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222882822" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222882822">(Jan 15 2021 at 16:26)</a>:</h4>
<p>You probably should run existing benchmarks too. Even if a particular search gets faster something else might get slowed down.</p>



<a name="222893739"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222893739" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222893739">(Jan 15 2021 at 17:31)</a>:</h4>
<p>I would assume the size of the elements in the btree will make a big difference to cache behaviour, and often binary search depends heavily on the branch predictor.  So general benchmarking is probably really hard here :/</p>



<a name="222893980"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222893980" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222893980">(Jan 15 2021 at 17:32)</a>:</h4>
<p>I haven't seen any discussion on capacity, except the one from years ago when B was a parameter changed into a constant.</p>
<p>Do you mean the benches under library/alloc/benches? They are somewhat arbitrary, and like all microbenchmarks, highly focused on read-only features. Changing capacity could have a relatively big impact on allocation, for better or worse (less capacity means more allocations but typically less wasted space, for instance a typical node has a usage of 6/11 = 54%, which would be 3/5 = 60%). In my experience, they behave consistently within a few %, provided you <a href="https://github.com/ssomers/cargo-benchcmp">pick the best from a few runs</a>.</p>
<p>A 5% change is nothing, you get 25% by <a href="https://github.com/rust-lang/rust/pull/74693">turning off some optimizations</a> (no, I did not mistype here). I bet you'd get more than 5% by simply inverting the current linear search, because usually in benchmarks, keys increase and you tend to come up with something that belongs at the end of the array.</p>



<a name="222894753"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222894753" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222894753">(Jan 15 2021 at 17:37)</a>:</h4>
<p><span class="user-mention" data-user-id="257813">@Stein Somers</span> thanks for the response. <a href="/user_uploads/4715/crir0IeMKBaV54lwjI6e47AK/timings.ods">Here</a> are some of the runs I did today, in case it interests you.</p>



<a name="222894866"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222894866" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222894866">(Jan 15 2021 at 17:38)</a>:</h4>
<p>Does the CI provide a possibility to run benches, e.g. as part of a PR, in a more "constant" environment than my laptop?</p>



<a name="222894880"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222894880" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222894880">(Jan 15 2021 at 17:38)</a>:</h4>
<blockquote>
<p>they behave consistently</p>
</blockquote>
<p>Wait, I mean: they behave consistently when running the same code. Any change in code can sometimes tip the balance and change the performance of multiple test cases tens of percents.</p>



<a name="222895094"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222895094" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222895094">(Jan 15 2021 at 17:39)</a>:</h4>
<p>I thought that with 59 benches, there would be a sufficient coverage of the different applications. Interesting.</p>



<a name="222895427"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222895427" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222895427">(Jan 15 2021 at 17:42)</a>:</h4>
<p><span aria-label="upside down" class="emoji emoji-1f643" role="img" title="upside down">:upside_down:</span> if only the CI provided the possibility to <a href="https://internals.rust-lang.org/t/x-py-how-to-benchmark-liballoc/11635/8">even check the syntax of benches</a>…</p>



<a name="222898714"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222898714" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222898714">(Jan 15 2021 at 18:04)</a>:</h4>
<p>Not sure if the ability to specify B (<code>with_b</code>) ever worked, but it was <a href="https://github.com/rust-lang/rust/issues/27795">deprecated</a>, <a href="https://github.com/rust-lang/rust/pull/30182">removed</a>, and its traces wiped out while <a href="https://github.com/rust-lang/rust/issues/27865">introducing parent pointers</a>. I do remember some discussion about it, but (as usual) can't find anything substantial in writing.</p>



<a name="222907507"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222907507" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222907507">(Jan 15 2021 at 19:00)</a>:</h4>
<p>I saw this note in one of those, which makes sense to me:</p>
<blockquote>
<p>I think this shouldn't go stable, this is definitely something that would be much better at the type level.</p>
</blockquote>
<p>So it sounds to me like the runtime config was removed, which totally makes sense.  With <code>min_const_generics</code> landing soon, you could try experimenting with making it configurable that way...</p>
<p>(Can a type parameter be marked unstable?)</p>



<a name="222908295"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222908295" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222908295">(Jan 15 2021 at 19:05)</a>:</h4>
<p>can const parameters have a default?</p>



<a name="222909058"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222909058" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222909058">(Jan 15 2021 at 19:10)</a>:</h4>
<p>Good question.  I have no idea.</p>



<a name="222911030"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222911030" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222911030">(Jan 15 2021 at 19:22)</a>:</h4>
<div class="codehilite"><pre><span></span><code>error[E0658]: default values for const generic parameters are experimental
 --&gt; src/lib.rs:3:29
  |
3 | pub type Foo&lt;const N: usize = 42&gt; = [u8; N];
  |                             ^^^^
  |
  = note: see issue #44580 &lt;https://github.com/rust-lang/rust/issues/44580&gt; for more information
  = help: add `#![feature(const_generics_defaults)]` to the crate attributes to enable
</code></pre></div>



<a name="222911076"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222911076" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222911076">(Jan 15 2021 at 19:23)</a>:</h4>
<p>that feature doesn't help though, and taken alone it errors unknown feature</p>



<a name="222911083"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222911083" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222911083">(Jan 15 2021 at 19:23)</a>:</h4>
<p>maybe it's a typo</p>



<a name="222911240"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222911240" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222911240">(Jan 15 2021 at 19:24)</a>:</h4>
<p>nevermind, it was my typo</p>



<a name="222911398"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222911398" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222911398">(Jan 15 2021 at 19:25)</a>:</h4>
<p>also need to allow <code>incomplete_features</code>, and give <code>42</code> an explicit type</p>



<a name="222911404"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222911404" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222911404">(Jan 15 2021 at 19:25)</a>:</h4>
<p>and then it ICEs</p>



<a name="222916544"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222916544" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222916544">(Jan 15 2021 at 20:00)</a>:</h4>
<p>I guess as a prototype it could just use a strategy type instead.  Might be nice anyway, to allow math defining the size</p>



<a name="222916627"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222916627" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222916627">(Jan 15 2021 at 20:00)</a>:</h4>
<p>(So there are more elements per node in a <code>BTreeSet&lt;u8&gt;</code> than a <code>BTreeSet&lt;[String; 7]&gt;</code>)</p>



<a name="222916782"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222916782" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222916782">(Jan 15 2021 at 20:02)</a>:</h4>
<p>this can also be explored in a crate, along the lines of <code>binary-heap-plus</code></p>



<a name="222916903"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222916903" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222916903">(Jan 15 2021 at 20:02)</a>:</h4>
<p>then a non-default const parameter is fine</p>



<a name="222916962"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222916962" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222916962">(Jan 15 2021 at 20:03)</a>:</h4>
<p>but computing based on <code>size_of</code> would also be neat</p>



<a name="222918372"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222918372" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222918372">(Jan 15 2021 at 20:11)</a>:</h4>
<p>Certainly C++ ended up moving away from using value template parameters for anything non-deduced, so one could argue that the strategy is always better even with full const generics support.</p>
<p>Crate-ification of the whole btree stuff might be interesting, like kindof happened with HashMap (if indirectly).</p>



<a name="222920592"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222920592" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222920592">(Jan 15 2021 at 20:27)</a>:</h4>
<p><span class="user-mention silent" data-user-id="323979">Bram van den Heuvel</span> <a href="#narrow/stream/122651-general/topic/Performance.20tuning.20BTree/near/222894753">said</a>:</p>
<blockquote>
<p><a href="/user_uploads/4715/crir0IeMKBaV54lwjI6e47AK/timings.ods">Here</a> are some of the runs I did today, in case it interests you.</p>
</blockquote>
<p>Wait, "capacity 6" and "capacity 8"? Those are odd because they're not odd. Capacity = 2B - 1 = always odd?</p>



<a name="222927877"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222927877" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222927877">(Jan 15 2021 at 21:28)</a>:</h4>
<p><span class="user-mention" data-user-id="257813">@Stein Somers</span> there is  a constant defined in the node module, I tweaked that.</p>



<a name="222928275"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222928275" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222928275">(Jan 15 2021 at 21:31)</a>:</h4>
<p><span class="user-mention" data-user-id="257813">@Stein Somers</span> I find it a bit suspect that all configurations seem to be better than the current state, which is why I fear that the tests weren't quite done right. The ugly copy-paste of bench output at the bottom is another run of the current state, it however gave the same results.</p>



<a name="222950479"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222950479" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222950479">(Jan 16 2021 at 01:47)</a>:</h4>
<p><span class="user-mention silent" data-user-id="323979">Bram van den Heuvel</span> <a href="#narrow/stream/122651-general/topic/Performance.20tuning.20BTree/near/222927877">said</a>:</p>
<blockquote>
<p><span class="user-mention silent" data-user-id="257813">Stein Somers</span> there is  a constant defined in the node module, I tweaked that.</p>
</blockquote>
<p>But which constant? If you tweak CAPACITY and it no longer equals 2B-1, some methods won't do what they're supposed to do. Unit tests show it but benchmarks usually don't test the results they obtain. I would expect some to crash, thanks to all unsafe code, but when I try B=6, CAPACITY=8, the benchmarks actually complete as if all is well, whatever they actually test.</p>
<p>When I try different values of B (4, 5, 6, 7, 8, 9, 10, 12, 16). on Windows x64, smaller than the default 6 is slower, bigger is faster, much bigger is slower again. The ideal would be 8 or 9.</p>
<p>The discussion I remembered is the first review discussion on <a href="https://github.com/rust-lang/rust/pull/17334/files#diff-0fbf0f551021f7c23fb61b403f5688ffaf8a767ceec795f73ea363a2f431ffb6">map.rs in the complete btree rewrite
#17334</a>. As far as I can tell, the number 6 was introduced at that point (over 6 years ago). Was it thoroughly assessed? There are clues that it wasn't: the comment next to it "//FIXME(Gankro): Tune this as a function of size_of&lt;K/V&gt;?", the fact that <a href="https://en.wikipedia.org/wiki/B-tree">the Wikipedia article</a> doesn't mention <code>B</code> as a parameter at all but speaks of order. Since then, data has been removed (like <code>b</code>) and some added (back pointers).</p>



<a name="222977589"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222977589" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222977589">(Jan 16 2021 at 11:59)</a>:</h4>
<p>@SteinSomers You're right, I meant to say I tuned different values of B, of course. Capacity being a function of B. I was careless in the communication, my apologies.</p>
<p>Interesting to see that values of 8 or 9 are best on your setup. What if you do binary search instead? Can you go even higher? <a href="https://github.com/vandenheuvel/rust/commit/abb2097f2a9103c212a9a3b516fc48f00ca760e8">Example</a></p>



<a name="222991631"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222991631" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222991631">(Jan 16 2021 at 16:46)</a>:</h4>
<p>I'll try later. Part of your binary search code looks like the previous slice access code. I've been trying to reconstruct exactly why we turned away from using a slice (because of <a href="https://github.com/rust-lang/rust/issues/73915">#73915</a>. It seems pretty unlikely that there is actual undefined behaviour in your binary search code, but it might violate the (proposed) stacked borrows rules. I hate it that I still don't seem to understand any of that stuff.</p>



<a name="222996455"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/222996455" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#222996455">(Jan 16 2021 at 18:08)</a>:</h4>
<p><span class="user-mention silent" data-user-id="323979">Bram van den Heuvel</span> <a href="#narrow/stream/122651-general/topic/Performance.20tuning.20BTree/near/222928275">said</a>:</p>
<blockquote>
<p>I find it a bit suspect that all configurations seem to be better than the current state, which is why I fear that the tests weren't quite done right.</p>
</blockquote>
<p>I agree it's suspect, unless perhaps if you're on 32 bit. This is (apart from colors that I can't seem to capture here) my difference between B=4 and B=6:</p>
<div class="codehilite"><pre><span></span><code>&gt;cargo-benchcmp.exe benchcmp b4 b6 --threshold 3
 name                                           b4 ns/iter  b6 ns/iter  diff ns/iter   diff %  speedup
 btree::map::clone_fat_100                      47,377      45,872            -1,505   -3.18%   x 1.03
 btree::map::clone_fat_100_and_drain_all        134,522     157,490           22,968   17.07%   x 0.85
 btree::map::clone_fat_100_and_drain_half       103,900     112,280            8,380    8.07%   x 0.93
 btree::map::clone_fat_100_and_pop_all          154,120     175,940           21,820   14.16%   x 0.88
 btree::map::clone_fat_100_and_remove_all       182,725     216,320           33,595   18.39%   x 0.84
 btree::map::clone_fat_100_and_remove_half      120,497     133,360           12,863   10.67%   x 0.90
 btree::map::clone_fat_val_100                  31,679      24,446            -7,233  -22.83%   x 1.30
 btree::map::clone_fat_val_100_and_clear        32,186      24,418            -7,768  -24.13%   x 1.32
 btree::map::clone_fat_val_100_and_drain_all    64,004      59,242            -4,762   -7.44%   x 1.08
 btree::map::clone_fat_val_100_and_drain_half   57,006      51,112            -5,894  -10.34%   x 1.12
 btree::map::clone_fat_val_100_and_into_iter    43,395      35,326            -8,069  -18.59%   x 1.23
 btree::map::clone_fat_val_100_and_pop_all      73,259      68,299            -4,960   -6.77%   x 1.07
 btree::map::clone_fat_val_100_and_remove_half  60,470      53,691            -6,779  -11.21%   x 1.13
 btree::map::clone_slim_100                     5,294       2,119             -3,175  -59.97%   x 2.50
 btree::map::clone_slim_100_and_clear           5,271       2,222             -3,049  -57.84%   x 2.37
 btree::map::clone_slim_100_and_drain_all       6,627       3,632             -2,995  -45.19%   x 1.82
 btree::map::clone_slim_100_and_drain_half      6,262       3,020             -3,242  -51.77%   x 2.07
 btree::map::clone_slim_100_and_into_iter       5,458       2,265             -3,193  -58.50%   x 2.41
 btree::map::clone_slim_100_and_pop_all         7,151       3,823             -3,328  -46.54%   x 1.87
 btree::map::clone_slim_100_and_remove_all      8,324       5,042             -3,282  -39.43%   x 1.65
 btree::map::clone_slim_100_and_remove_half     6,550       3,401             -3,149  -48.08%   x 1.93
 btree::map::clone_slim_10k                     290,405     262,550          -27,855   -9.59%   x 1.11
 btree::map::clone_slim_10k_and_clear           287,933     258,333          -29,600  -10.28%   x 1.11
 btree::map::clone_slim_10k_and_drain_all       416,035     391,235          -24,800   -5.96%   x 1.06
 btree::map::clone_slim_10k_and_drain_half      395,475     359,150          -36,325   -9.19%   x 1.10
 btree::map::clone_slim_10k_and_into_iter       286,853     258,896          -27,957   -9.75%   x 1.11
 btree::map::clone_slim_10k_and_pop_all         454,875     424,620          -30,255   -6.65%   x 1.07
 btree::map::clone_slim_10k_and_remove_all      619,797     592,790          -27,007   -4.36%   x 1.05
 btree::map::clone_slim_10k_and_remove_half     577,440     553,130          -24,310   -4.21%   x 1.04
 btree::map::find_rand_100                      12          13                     1    8.33%   x 0.92
 btree::map::find_rand_10_000                   59          56                    -3   -5.08%   x 1.05
 btree::map::find_seq_100                       11          12                     1    9.09%   x 0.92
 btree::map::find_seq_10_000                    35          37                     2    5.71%   x 0.95
 btree::map::first_and_last_0                   12          10                    -2  -16.67%   x 1.20
 btree::map::first_and_last_100                 42          49                     7   16.67%   x 0.86
 btree::map::first_and_last_10k                 85          61                   -24  -28.24%   x 1.39
 btree::map::insert_rand_100                    40          45                     5   12.50%   x 0.89
 btree::map::insert_rand_10_000                 40          43                     3    7.50%   x 0.93
 btree::map::insert_seq_100                     45          49                     4    8.89%   x 0.92
 btree::map::iter_1m                            14,865      13,879              -986   -6.63%   x 1.07
 btree::map::iteration_1000                     3,418       3,535                117    3.42%   x 0.97
 btree::map::iteration_100000                   618,140     510,870         -107,270  -17.35%   x 1.21
 btree::map::iteration_mut_1000                 3,800       3,982                182    4.79%   x 0.95
 btree::map::iteration_mut_100000               625,930     548,390          -77,540  -12.39%   x 1.14
 btree::map::iteration_mut_20                   70          67                    -3   -4.29%   x 1.04
 btree::map::range_included_excluded            529,918     443,190          -86,728  -16.37%   x 1.20
 btree::map::range_included_included            441,616     522,970           81,354   18.42%   x 0.84
 btree::map::range_included_unbounded           143,018     179,338           36,320   25.40%   x 0.80
 btree::set::clone_100                          5,283       1,918             -3,365  -63.69%   x 2.75
 btree::set::clone_100_and_clear                5,296       1,948             -3,348  -63.22%   x 2.72
 btree::set::clone_100_and_drain_all            6,328       2,921             -3,407  -53.84%   x 2.17
 btree::set::clone_100_and_drain_half           6,103       2,523             -3,580  -58.66%   x 2.42
 btree::set::clone_100_and_into_iter            5,224       1,884             -3,340  -63.94%   x 2.77
 btree::set::clone_100_and_pop_all              5,924       2,546             -3,378  -57.02%   x 2.33
 btree::set::clone_100_and_remove_all           7,086       3,608             -3,478  -49.08%   x 1.96
 btree::set::clone_100_and_remove_half          5,943       2,604             -3,339  -56.18%   x 2.28
 btree::set::clone_10k                          274,580     227,957          -46,623  -16.98%   x 1.20
 btree::set::clone_10k_and_clear                277,315     226,945          -50,370  -18.16%   x 1.22
 btree::set::clone_10k_and_drain_all            380,330     329,383          -50,947  -13.40%   x 1.15
 btree::set::clone_10k_and_drain_half           362,025     309,520          -52,505  -14.50%   x 1.17
 btree::set::clone_10k_and_into_iter            277,903     226,372          -51,531  -18.54%   x 1.23
 btree::set::clone_10k_and_pop_all              356,085     293,573          -62,512  -17.56%   x 1.21
 btree::set::clone_10k_and_remove_all           516,590     438,045          -78,545  -15.20%   x 1.18
 btree::set::clone_10k_and_remove_half          529,180     479,260          -49,920   -9.43%   x 1.10
 btree::set::difference_random_100_vs_10k       3,162       3,298                136    4.30%   x 0.96
 btree::set::difference_random_10k_vs_100       64,625      59,959            -4,666   -7.22%   x 1.08
 btree::set::difference_random_10k_vs_10k       215,760     196,224          -19,536   -9.05%   x 1.10
 btree::set::difference_staggered_100_vs_10k    2,331       2,231               -100   -4.29%   x 1.04
 btree::set::intersection_100_pos_vs_10k_neg    19          18                    -1   -5.26%   x 1.06
 btree::set::intersection_10k_neg_vs_10k_pos    20          19                    -1   -5.00%   x 1.05
 btree::set::intersection_10k_pos_vs_10k_neg    20          19                    -1   -5.00%   x 1.05
 btree::set::intersection_random_10k_vs_10k     192,072     167,036          -25,036  -13.03%   x 1.15
 btree::set::intersection_staggered_100_vs_100  697         653                  -44   -6.31%   x 1.07
 btree::set::intersection_staggered_100_vs_10k  2,152       2,026               -126   -5.86%   x 1.06
 btree::set::intersection_staggered_10k_vs_10k  67,997      62,555            -5,442   -8.00%   x 1.09
 btree::set::is_subset_100_vs_100               544         509                  -35   -6.43%   x 1.07
 btree::set::is_subset_100_vs_10k               1,425       1,775                350   24.56%   x 0.80
 btree::set::is_subset_10k_vs_10k               63,833      59,613            -4,220   -6.61%   x 1.07
</code></pre></div>
<p>The mutable benchmarks (those starting with <code>clone_</code> are massively better, as expected, because there are more nodes to clone. <code>clone_fat_</code> seems to fare well, but these are among those benchmarks that tend to change their mind whenever something changes. A few immutable benchmark fare well too, but the mood is overwhelmingly for B=6.</p>



<a name="223200429"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223200429" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223200429">(Jan 19 2021 at 08:57)</a>:</h4>
<p><span class="user-mention silent" data-user-id="257813">Stein Somers</span> <a href="#narrow/stream/122651-general/topic/Performance.20tuning.20BTree/near/222991631">said</a>:</p>
<blockquote>
<p>I'll try later. Part of your binary search code looks like the previous slice access code. I've been trying to reconstruct exactly why we turned away from using a slice (because of <a href="https://github.com/rust-lang/rust/issues/73915">#73915</a>. It seems pretty unlikely that there is actual undefined behaviour in your binary search code, but it might violate the (proposed) stacked borrows rules. I hate it that I still don't seem to understand any of that stuff.</p>
</blockquote>
<p>I'm afraid I don't understand it either!</p>



<a name="223200509"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223200509" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223200509">(Jan 19 2021 at 08:58)</a>:</h4>
<p><span class="user-mention silent" data-user-id="257813">Stein Somers</span> <a href="#narrow/stream/122651-general/topic/Performance.20tuning.20BTree/near/222996455">said</a>:</p>
<blockquote>
<p><span class="user-mention silent" data-user-id="323979">Bram van den Heuvel</span> <a href="#narrow/stream/122651-general/topic/Performance.20tuning.20BTree/near/222928275">said</a>:</p>
<blockquote>
<p>I find it a bit suspect that all configurations seem to be better than the current state, which is why I fear that the tests weren't quite done right.</p>
</blockquote>
<p>I agree it's suspect, unless perhaps if you're on 32 bit. This is (apart from colors that I can't seem to capture here) my difference between B=4 and B=6:</p>
<div class="codehilite"><pre><span></span><code>&gt;cargo-benchcmp.exe benchcmp b4 b6 --threshold 3
 name                                           b4 ns/iter  b6 ns/iter  diff ns/iter   diff %  speedup
 btree::map::clone_fat_100                      47,377      45,872            -1,505   -3.18%   x 1.03
 btree::map::clone_fat_100_and_drain_all        134,522     157,490           22,968   17.07%   x 0.85
 btree::map::clone_fat_100_and_drain_half       103,900     112,280            8,380    8.07%   x 0.93
 btree::map::clone_fat_100_and_pop_all          154,120     175,940           21,820   14.16%   x 0.88
 btree::map::clone_fat_100_and_remove_all       182,725     216,320           33,595   18.39%   x 0.84
 btree::map::clone_fat_100_and_remove_half      120,497     133,360           12,863   10.67%   x 0.90
 btree::map::clone_fat_val_100                  31,679      24,446            -7,233  -22.83%   x 1.30
 btree::map::clone_fat_val_100_and_clear        32,186      24,418            -7,768  -24.13%   x 1.32
 btree::map::clone_fat_val_100_and_drain_all    64,004      59,242            -4,762   -7.44%   x 1.08
 btree::map::clone_fat_val_100_and_drain_half   57,006      51,112            -5,894  -10.34%   x 1.12
 btree::map::clone_fat_val_100_and_into_iter    43,395      35,326            -8,069  -18.59%   x 1.23
 btree::map::clone_fat_val_100_and_pop_all      73,259      68,299            -4,960   -6.77%   x 1.07
 btree::map::clone_fat_val_100_and_remove_half  60,470      53,691            -6,779  -11.21%   x 1.13
 btree::map::clone_slim_100                     5,294       2,119             -3,175  -59.97%   x 2.50
 btree::map::clone_slim_100_and_clear           5,271       2,222             -3,049  -57.84%   x 2.37
 btree::map::clone_slim_100_and_drain_all       6,627       3,632             -2,995  -45.19%   x 1.82
 btree::map::clone_slim_100_and_drain_half      6,262       3,020             -3,242  -51.77%   x 2.07
 btree::map::clone_slim_100_and_into_iter       5,458       2,265             -3,193  -58.50%   x 2.41
 btree::map::clone_slim_100_and_pop_all         7,151       3,823             -3,328  -46.54%   x 1.87
 btree::map::clone_slim_100_and_remove_all      8,324       5,042             -3,282  -39.43%   x 1.65
 btree::map::clone_slim_100_and_remove_half     6,550       3,401             -3,149  -48.08%   x 1.93
 btree::map::clone_slim_10k                     290,405     262,550          -27,855   -9.59%   x 1.11
 btree::map::clone_slim_10k_and_clear           287,933     258,333          -29,600  -10.28%   x 1.11
 btree::map::clone_slim_10k_and_drain_all       416,035     391,235          -24,800   -5.96%   x 1.06
 btree::map::clone_slim_10k_and_drain_half      395,475     359,150          -36,325   -9.19%   x 1.10
 btree::map::clone_slim_10k_and_into_iter       286,853     258,896          -27,957   -9.75%   x 1.11
 btree::map::clone_slim_10k_and_pop_all         454,875     424,620          -30,255   -6.65%   x 1.07
 btree::map::clone_slim_10k_and_remove_all      619,797     592,790          -27,007   -4.36%   x 1.05
 btree::map::clone_slim_10k_and_remove_half     577,440     553,130          -24,310   -4.21%   x 1.04
 btree::map::find_rand_100                      12          13                     1    8.33%   x 0.92
 btree::map::find_rand_10_000                   59          56                    -3   -5.08%   x 1.05
 btree::map::find_seq_100                       11          12                     1    9.09%   x 0.92
 btree::map::find_seq_10_000                    35          37                     2    5.71%   x 0.95
 btree::map::first_and_last_0                   12          10                    -2  -16.67%   x 1.20
 btree::map::first_and_last_100                 42          49                     7   16.67%   x 0.86
 btree::map::first_and_last_10k                 85          61                   -24  -28.24%   x 1.39
 btree::map::insert_rand_100                    40          45                     5   12.50%   x 0.89
 btree::map::insert_rand_10_000                 40          43                     3    7.50%   x 0.93
 btree::map::insert_seq_100                     45          49                     4    8.89%   x 0.92
 btree::map::iter_1m                            14,865      13,879              -986   -6.63%   x 1.07
 btree::map::iteration_1000                     3,418       3,535                117    3.42%   x 0.97
 btree::map::iteration_100000                   618,140     510,870         -107,270  -17.35%   x 1.21
 btree::map::iteration_mut_1000                 3,800       3,982                182    4.79%   x 0.95
 btree::map::iteration_mut_100000               625,930     548,390          -77,540  -12.39%   x 1.14
 btree::map::iteration_mut_20                   70          67                    -3   -4.29%   x 1.04
 btree::map::range_included_excluded            529,918     443,190          -86,728  -16.37%   x 1.20
 btree::map::range_included_included            441,616     522,970           81,354   18.42%   x 0.84
 btree::map::range_included_unbounded           143,018     179,338           36,320   25.40%   x 0.80
 btree::set::clone_100                          5,283       1,918             -3,365  -63.69%   x 2.75
 btree::set::clone_100_and_clear                5,296       1,948             -3,348  -63.22%   x 2.72
 btree::set::clone_100_and_drain_all            6,328       2,921             -3,407  -53.84%   x 2.17
 btree::set::clone_100_and_drain_half           6,103       2,523             -3,580  -58.66%   x 2.42
 btree::set::clone_100_and_into_iter            5,224       1,884             -3,340  -63.94%   x 2.77
 btree::set::clone_100_and_pop_all              5,924       2,546             -3,378  -57.02%   x 2.33
 btree::set::clone_100_and_remove_all           7,086       3,608             -3,478  -49.08%   x 1.96
 btree::set::clone_100_and_remove_half          5,943       2,604             -3,339  -56.18%   x 2.28
 btree::set::clone_10k                          274,580     227,957          -46,623  -16.98%   x 1.20
 btree::set::clone_10k_and_clear                277,315     226,945          -50,370  -18.16%   x 1.22
 btree::set::clone_10k_and_drain_all            380,330     329,383          -50,947  -13.40%   x 1.15
 btree::set::clone_10k_and_drain_half           362,025     309,520          -52,505  -14.50%   x 1.17
 btree::set::clone_10k_and_into_iter            277,903     226,372          -51,531  -18.54%   x 1.23
 btree::set::clone_10k_and_pop_all              356,085     293,573          -62,512  -17.56%   x 1.21
 btree::set::clone_10k_and_remove_all           516,590     438,045          -78,545  -15.20%   x 1.18
 btree::set::clone_10k_and_remove_half          529,180     479,260          -49,920   -9.43%   x 1.10
 btree::set::difference_random_100_vs_10k       3,162       3,298                136    4.30%   x 0.96
 btree::set::difference_random_10k_vs_100       64,625      59,959            -4,666   -7.22%   x 1.08
 btree::set::difference_random_10k_vs_10k       215,760     196,224          -19,536   -9.05%   x 1.10
 btree::set::difference_staggered_100_vs_10k    2,331       2,231               -100   -4.29%   x 1.04
 btree::set::intersection_100_pos_vs_10k_neg    19          18                    -1   -5.26%   x 1.06
 btree::set::intersection_10k_neg_vs_10k_pos    20          19                    -1   -5.00%   x 1.05
 btree::set::intersection_10k_pos_vs_10k_neg    20          19                    -1   -5.00%   x 1.05
 btree::set::intersection_random_10k_vs_10k     192,072     167,036          -25,036  -13.03%   x 1.15
 btree::set::intersection_staggered_100_vs_100  697         653                  -44   -6.31%   x 1.07
 btree::set::intersection_staggered_100_vs_10k  2,152       2,026               -126   -5.86%   x 1.06
 btree::set::intersection_staggered_10k_vs_10k  67,997      62,555            -5,442   -8.00%   x 1.09
 btree::set::is_subset_100_vs_100               544         509                  -35   -6.43%   x 1.07
 btree::set::is_subset_100_vs_10k               1,425       1,775                350   24.56%   x 0.80
 btree::set::is_subset_10k_vs_10k               63,833      59,613            -4,220   -6.61%   x 1.07
</code></pre></div>
<p>The mutable benchmarks (those starting with <code>clone_</code> are massively better, as expected, because there are more nodes to clone. <code>clone_fat_</code> seems to fare well, but these are among those benchmarks that tend to change their mind whenever something changes. A few immutable benchmark fare well too, but the mood is overwhelmingly for B=6.</p>
</blockquote>
<p>I'm not on 32 bit. I repeated the benches for the current state once and got similar results though.</p>



<a name="223385334"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223385334" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223385334">(Jan 20 2021 at 15:07)</a>:</h4>
<p><span class="user-mention silent" data-user-id="323979">Bram van den Heuvel</span> [said]<a href="https://github.com/vandenheuvel/rust/commit/abb2097f2a9103c212a9a3b516fc48f00ca760e8">Example</a></p>
<p>Never mind stacked borrow rules, that code is broken. The keys to search in are not<code>self.keys</code> but <code>self.keys[..len]</code>. So your binary search is predominantly reading random, probably zero-initialized memory.</p>



<a name="223418113"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223418113" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223418113">(Jan 20 2021 at 18:56)</a>:</h4>
<p>I'm somewhat sure what was wrong with the previous slice access code and fixed it, and supplanted the good part of your binary search on top of it at <a href="https://github.com/ssomers/rust/tree/btree_binary_search">my btree_binary_search branch</a>. Time to start measuring.</p>



<a name="223541031"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223541031" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223541031">(Jan 21 2021 at 17:17)</a>:</h4>
<p>With the right code, from my measurements, binary search doesn't help and instead somewhat harms performance. Also, inverting the linear search also has a slight penalty. My earlier diagnosis that for linear search, B=8 or 9 is better is a bit dubious: mutable tests are a lot better, obviously because there are fewer allocations, but immutable tests are on the decline above 7. Also, for 32-bit, that's above 6. So, on my Intel Core i5-9400F CPU, it seems the current code and B=6 is the best for 32 bit builds, B=7 would be better for 64 bit builds only.</p>



<a name="223880324"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223880324" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Bram van den Heuvel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223880324">(Jan 25 2021 at 10:49)</a>:</h4>
<p><span class="user-mention" data-user-id="257813">@Stein Somers</span> did you also try binary search for larger values of <code>B</code>? Maybe it starts to shine there.<br>
Thanks regardless for the more elaborate analysis and clearing this up.</p>



<a name="223882117"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223882117" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223882117">(Jan 25 2021 at 11:08)</a>:</h4>
<p>I tried up to B=12. The results clearly say binary search is worse, much more than they say that B=12 does worse than B=6 with linear search. B=12 pretty much means only 12 elements per array in these benchmarks. I'll try something bigger because clearly there should be some point at which binary search pays off.</p>



<a name="223927330"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Performance%20tuning%20BTree/near/223927330" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Stein Somers <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Performance.20tuning.20BTree.html#223927330">(Jan 25 2021 at 17:00)</a>:</h4>
<p>Another surprise came up: on Windows, the size limit per key-value pair is &lt; 24KB, and this reduces linearly with increasing B. So some of the benchmarks bail out with stack overflow.</p>
<p>Anyway, for B=24, the linear and binary seem on par. For B=36, it's like linear takes the edge again. But at B=48, linear is clearly unable to catch up. At B=60, linear is eating binary's dust.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>